#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

const int N = 35;
class Solution {
public:
    int f[N];

    int dfs(int n)
    {
        if (f[n] != -1)return f[n];
        if (n == 0 || n == 1)return n;
        f[n] = dfs(n - 1) + dfs(n - 2);
        return f[n];
    }
    int fib(int n) {
        memset(f, -1, sizeof(f));
        return dfs(n);
    }
};